package demo03;

import java.util.HashSet;
import java.util.Set;

//0~n-1中缺失的数字
//方法一:二分查找
public class Solution {
    public static int[] arr = new int[]{0,1,2,4,5,6,7};
    public int find(int[] arr){
        int left = 0;
        int right = arr.length - 1;
        while (left < right){
            int mid = left + (right - left) / 2;
            if(arr[mid] == mid) left = mid + 1;
            if(arr[mid] != mid) right = mid;
        }
        if(arr[left] == left) return left + 1;
        return left;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.find(arr));
    }
}
//方法二:位运算
//public class Solution {
//    public static int[] arr = new int[]{0,1,2,4,5,6,7};
//    public int find(int[] arr){
//        int L = arr.length;
//        int num = 0;
//        //先异或正确的序列
//        for (int i = 0; i <= L; i++) {
//            num = i ^ num;
//        }
//        //再异或数组
//        for (int i = 0; i < L ; i++) {
//            num = num ^ arr[i];
//        }
//        return num;
//    }
//
//    public static void main(String[] args) {
//        Solution solution = new Solution();
//        System.out.println(solution.find(arr));
//    }
//}
//方法三:哈希表
//public class Solution {
//    public static int[] arr = new int[]{0,1,2,4,5,6,7};
//    public int find(int[] arr){
//        int n = arr.length + 1; // 完整范围是0~n-1
//        // 把数组元素存入哈希集合
//        Set<Integer> set = new HashSet<>();
//        for (int num : arr) {
//            set.add(num);
//        }
//        // 遍历0~n-1，找不在集合中的数
//        for (int i = 0; i < n; i++) {
//            if (!set.contains(i)) {
//                return i;
//            }
//        }
//        return -1; // 逻辑上不会走到这里
//    }
//
//    public static void main(String[] args) {
//        Solution solution = new Solution();
//        System.out.println(solution.find(arr));
//    }
//}
//
